"""
题目：二叉树的直径是指树中任意两个节点之间最长路径的长度（路径上的边数），计算该直径。
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameter_of_binary_tree(root):
    """计算二叉树的直径（递归实现）"""
    max_diameter = 0  # 存储全局最大直径（边数）
    def dfs(node):
        nonlocal max_diameter
        if not node:
            return 0  # 空节点的深度为0（节点数）
        # 递归计算左右子树的深度（节点数）
        left_depth = dfs(node.left)
        right_depth = dfs(node.right)
        # 当前节点的直径（边数）= 左子树深度 + 右子树深度（节点数转边数）
        current_diameter = left_depth + right_depth
        # 更新全局最大直径
        if current_diameter > max_diameter:
            max_diameter = current_diameter
        # 返回当前节点的深度（节点数）：1（自身）+ 子树最大深度
        return 1 + max(left_depth, right_depth)
    dfs(root)
    return max_diameter

# 创建二叉树（通用函数，下同）
def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root

# 测试
root1 = create_binary_tree([1, 2, 3, 4, 5])
# 树结构：
#       1
#      / \
#     2   3
#    / \
#   4   5
print(diameter_of_binary_tree(root1))  # 输出: 3（路径4-2-5或4-2-1-3，边数3）
root2 = create_binary_tree([1, 2])
print(diameter_of_binary_tree(root2))  # 输出: 1（路径1-2，边数1）